<?php
/**
 * <https://y.st./>
 * Copyright © 2017 Alex Yst <mailto:copyright@y.st>
 * 
 * This program is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 * 
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
 * GNU General Public License for more details.
 * 
 * You should have received a copy of the GNU General Public License
 * along with this program. If not, see <https://www.gnu.org./licenses/>.
**/

$xhtml = array(
	'<{title}>' => 'Complexity',
	'<{subtitle}>' => 'Written in <span title="Software Engineering 1">CS 2401</span>, finalised on 2017-12-27',
	'<{copyright year}>' => '2017',
	'takedown' => '2017-11-01',
	'<{body}>' => <<<END
<p>
	At first, it looks like we have two separate algorithms to chart and graph.
	That gives us a flowchart like this:
</p>
<img src="file:///y.st./source/y.st./static/img/CC_BY-SA_4.0/y.st./coursework/CS2401/program_flow_-_two-part.png" alt="Split flowchart" class="framed-centred-image" width="816" height="374"/>
<p>
	Using that flowchart to build the complexity graph, we end up with the following:
</p>
<img src="file:///y.st./source/y.st./static/img/CC_BY-SA_4.0/y.st./coursework/CS2401/program_complexity_-_two-part.png" alt="Split complexity graph" class="framed-centred-image" width="386" height="245"/>
<p>
	However, that&apos;s not a very accurate depiction of the algorithm.
	If this pseudocode were representative of a module, this complexity graph would accurately represent it.
	We&apos;re not measuring the complexity of the module though, or of the code that implements the algorithm, but the complexity of the individual algorithm itself.
	We should collapse the chart and show the flow of the algorithm itself; that is, we should make it a single connected component.
	Though not explained by our textbook, a connected component is made up of all components in the chart that are connected (Wikipedia, n.d.).
	Collapsing the <code>PARTITION()</code> subroutine into the <code>QUICKSORT()</code> algorithm&apos;s flowchart is easy.
	The difficult part is recursively collapsing the <code>QUICKSORT()</code> algorithm&apos;s flowchart into itself.
	Thankfully, we don&apos;t have to even <strong>*attempt*</strong> such a challenging feat.
	Our textbook didn&apos;t cover how to deal with recursion when calculating complexity, but a couple sources say recursion doesn&apos;t directly add complexity.
	As long as we account for the guard condition, we can ignore the recursive function call (O&apos;Dennehy, n.d.) (Ron, 2011).
	With that in mind, there&apos;s no reason to recursively collapse the chart into itself in any way.
	This leaves us with a flowchart such as the following:
</p>
<img src="file:///y.st./source/y.st./static/img/CC_BY-SA_4.0/y.st./coursework/CS2401/program_flow_-_one-part.png" alt="Flowchart" class="framed-centred-image" width="934" height="321"/>
<p>
	Using this new, one-piece flowchart, we end up with this slightly-simpler complexity graph:
</p>
<img src="file:///y.st./source/y.st./static/img/CC_BY-SA_4.0/y.st./coursework/CS2401/program_complexity_-_one-part.png" alt="Complexity graph" class="framed-centred-image" width="328" height="237"/>
<p>
	This gives us a total of nine nodes, eleven edges, and one connected component.
	It&apos;s important to note that because we&apos;re mapping a single algorithm, it&apos;s only possible to have one connected component.
	If we have any more than that, we&apos;ve done something wrong.
	The textbook presents us with three formulas for finding variations of the cyclomatic complexity.
	In this assignment, we were to find the cyclomatic complexity of the provided algorithm, but we weren&apos;t instructed as to which equation to use.
</p>
<h2>V(G) = e - n + 2</h2>
<p>
	The text book proposes this formula first, but doesn&apos;t specify where it came from.
	While the concept of cyclomatic complexity came from Thomas McCabe, this particular formula isn&apos;t attributed to them and could have come from elsewhere, especially given that the next formula <strong>*is*</strong> attributed to McCabe.
	Using this formula, we calculate that <strong>we have a cyclomatic complexity of four</strong>.
</p>
<h2>V(G) = e - n + 2 * p</h2>
<p>
	This is the original formula proposed by Thomas McCabe.
	Using the original formula, we see <strong>we have a cyclomatic complexity of four</strong>, just like with the previous equation.
	This is because we collapsed the algorithm and looked at the flow as a whole.
	The first equation proposed by the textbook is identical to McCabe&apos;s original except that it assumes the graph has only one connected component, even when it has several.
</p>
<h2>V<sub>LI</sub>(G) = e - n + p + 1</h2>
<p>
	This alternative formula was proposed by Henderson-Sellers and Tegarden.
	This formula gives less of a penalty for having extra connected components, but it still imposes a penalty.
	The base case though, having one connected component, still provides us with the same answer as with the other two equations.
	Again, because we properly collapsed our flowchart, we find <strong>we have a cyclomatic complexity of four</strong>.
</p>
<h2>Conclusion</h2>
<p>
	As long as we look at the algorithm as a whole, it doesn&apos;t matter which of the three complexity-calculation formulas we use.
	We&apos;ll always arrive at the same answer.
	This is what we should expect when looking at single algorithms and programs.
	If we look at something that doesn&apos;t have a flow on its own, such as a library that is hooked into by other programs and algorithms, we might have more connected components.
	As such, which complexity-calculation equation we use determines how much of a penalty we give ourselves for having these separate components lumped together.
	That said, separate components should probably be placed in their own separate modules; if these three equations are yielding different responses (in other words, if we have more than one connected component), it&apos;s probably time to modularise.
</p>
<div class="APA_references">
	<h2>References:</h2>
	<p>
		O&apos;Dennehy, D. (n.d.). What is Cyclomatic complexity of recursive factorial problem. Retrieved from <a href="https://www.answers.com/Q/What_is_Cyclomatic_complexity_of_recursive_factorial_problem"><code>https://www.answers.com/Q/What_is_Cyclomatic_complexity_of_recursive_factorial_problem</code></a>
	</p>
	<p>
		Ron. (2011, September 22). Does recursive method increase cyclomatric complexity. Retrieved from <a href="https://stackoverflow.com/questions/3528491/does-recursive-method-increase-cyclomatric-complexity#answer-7509542"><code>https://stackoverflow.com/questions/3528491/does-recursive-method-increase-cyclomatric-complexity#answer-7509542</code></a>
	</p>
	<p>
		Wikipedia. (2017, December 4). Connected component (graph theory). Retrieved from <a href="https://en.wikipedia.org/wiki/Connected_component_%28graph_theory%29"><code>https://en.wikipedia.org/wiki/Connected_component_%28graph_theory%29</code></a>
	</p>
</div>
END
);
